#ifndef __LockFreeQueue_H__
#define __LockFreeQueue_H__

#include <atomic>

template <class T>
class LockFreeQueue
{
    struct Node {
        T val;
        // 对每一个指针操作时都需要是原子的，也就是指针的指向要么发生变化，要么没有变化，不会产生第三种结果。
        std::atomic<Node*> next;

        Node(const T& x) : val(x), next(nullptr) {}
    };

public:
    // 队列设置一个哑节点，这样能更好的判断队列是否为空。
    LockFreeQueue() {
        head = tail = new Node(T());
    }

    ~LockFreeQueue() {
        Node* p = head;
        while (p) {
            Node* post = p->next;
            delete p;
            p = post;
        }
    }

    // 无锁队列禁止拷贝与赋值
    LockFreeQueue(const LockFreeQueue<T>&) = delete;
    LockFreeQueue& operator=(const LockFreeQueue<T>&) = delete;

    // 入队
    void enQueue(const T& x) {
        Node* new_node = new Node(x); // 要插入的新值
        Node* old_tail = nullptr; 
        Node* null_node = nullptr;

        // 看一下队尾的下一个节点是否是我预想的nullptr，如果是我就插入，如果不是我就轮询直到尾节点的下一个为nullptr
        do {
            // load()：取出atomic对象指向的值
            old_tail = tail.load();

            // 如果内存中的值和参数一expected相同，那么替换为参数二val，成功返回true
            // compare_exchange_weak(T& expected, T val, memory_order sync = memory_order_seq_cst)
        } while (!old_tail->next.compare_exchange_weak(null_node, new_node));

        // 尾指针后移
        tail.compare_exchange_weak(old_tail, new_node);
    }

    // 出队
    T deQueue() {
        Node* dummy_node = head.load();
        T head_val;

        do {
            Node* p = dummy_node->next;
            if (p == nullptr) {
                // 队列为空
                return T();
            }
            else {
                head_val = p->val;
            }
        // 查看现在队列的头head是否是期望的dummy_node，如果是则取走值，将头节点修改为dummy_node的下一个
        } while (!head.compare_exchange_weak(dummy_node, dummy_node->next));

        delete dummy_node;
        
        return head_val;
    }

    // 判空
    bool isEmpty() {
        return head.load() == tail.load();
    }

private:
    std::atomic<Node*> head;
    std::atomic<Node*> tail;
};

#endif
